package Datastruct.Kruskal;

public class DjiestelaAlgorithm {
    public static int Maxvalue = 100000;


    public static void main(String[] args) {
        int vertex = 7;

        int edge = 10;

        int[][] matrix = new int[vertex][vertex];
        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                matrix[i][j] = Maxvalue;
            }
        }

        matrix[0][1] = 6;
        matrix[1][2] = 5;
        matrix[0][3] = 2;
        matrix[3][1] = 7;
        matrix[3][4] = 5;
        matrix[1][2] = 5;
        matrix[1][5] = 3;
        matrix[4][5] = 5;
        matrix[5][4] = 2;
        matrix[4][6] = 1;

        int sourse = 0;
        dijstra(matrix, sourse);

    }

    //地杰斯特拉算法
    public static void dijstra(int[][] matrix, int spurse) {
        //最短路径长度
        int[] shortext = new int[matrix.length];

        //判断是否能够算出改顶点的最短距离
        int[] visited = new int[matrix.length];
        //拼接有效路径
        String[] path = new String[matrix.length];

        for (int i = 0; i < matrix.length; i++) {
            path[i] = new String(spurse + "-->" + i);
        }
        //原点有效距离
        shortext[spurse] = 0;
        //有效路径
        visited[spurse] = 1;


        for (int i = 1; i < matrix.length; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;
            for (int j = 0; j < matrix.length; j++) {
                if (visited[j] == 0 && matrix[spurse][j] < min) {
                    min = matrix[spurse][j];
                    index = j;

                }
            }

            shortext[index] = min;
            visited[index] = 1;   //表示找到最短距离

            for (int m = 0; m < matrix.length; m++) {
                if (visited[m] == 0 && matrix[spurse][index] + matrix[index][m] < matrix[spurse][m]) {
                    matrix[spurse][m] = matrix[spurse][index] + matrix[index][m];
                    path[m] = path[index] + "-->" + m;
                }
            }
        }


        for (int i = 0; i < matrix.length; i++) {
            if (i != spurse) {
                if (shortext[i] == Maxvalue) {
                    System.out.println(spurse + "到" + i + "不可以直接到达");
                } else {
                    System.out.println(spurse + "到" + i + "的最短路径是" + path[i] + "最短距离是：" + shortext[i]);
                }
            }

        }


    }

}
